#
# @lc app=leetcode.cn id=5 lang=python3
#
# [5] 最长回文子串
#

# @lc code=start
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n=len(s)
        if n<2: # 一个字符串是回文串
            return s
        
        max_len=1 # 回文串的最大长度
        begin=0 # 回文串的开始位置
        # dp[i][j]字符串s[i...j]是否是回文串
        dp = [[False]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        
        # 递推开始
        # 先枚举字串长度
        for length in range(2, n+1):
            # 再枚举左边界
            for i in range(n):
                j = i+length-1 # 右边界
                if j>=n: # 右下标越界
                    break
                # 回文串递推
                if s[i] == s[j]:
                    if j-i<3:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                else:
                    dp[i][j]=False
                # 保存最长回文子串
                if dp[i][j]==True and j-i+1>max_len:
                    max_len=j-i+1 # 注意此处j-i+1
                    begin=i
        
        return s[begin:begin+max_len]
# 注意细节点,字符串长度和字符串下标差值之间的关系
# j=i+length-1
# j-i=length-1<=2 -> length<=3
# length=j-i+1
        
# @lc code=end

